package leetcode.hot100;

import java.util.Stack;

@SuppressWarnings("all")
public class _20_有效的括号_栈 {

    // s = "()[]{}" 为true
    // s = "(]"     为false
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) return true;
        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (char aChar : chars) {
            if (aChar == '(' || aChar == '[' || aChar == '{'){
                stack.push(aChar);
            }else{
                // 如果最终满足有效的括号，那么在弹出括号之前，栈一定不为空
                // 包含了处理开头就是右括号的情况
                if (stack.isEmpty()) return false;
                if (aChar == ')' && stack.pop() != '(') return false;
                if (aChar == ']' && stack.pop() != '[') return false;
                if (aChar == '}' && stack.pop() != '{') return false;
            }
        }
        // 针对只有左括号的特殊情况
        return stack.isEmpty();
    }
}
